 #include<iostream>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<cmath>
#include<ctime>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<limits>
using namespace std;
template<class T>void showp(T a, int n){for(int i=0; i<n; ++i) cout<<a[i].x<<" "<<a[i].y<<' '; cout<<endl;}
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
#define see(x)(cerr<<"[line:"<<__LINE__<<" "<<#x<<" "<<x<<endl)
#define se(x) cerr<<x<<" "
#define sep(a) printf("%.3lf %.3lf\n",a.x,a.y);
const int maxn = 40024;
inline int rd(){int x;scanf("%d",&x);return x;}
int n,m;
const double eps=1e-6;
const double inf=1e20;
const double pi=acos(-1.0);
int dcmp(double t)
{return (t>eps)-(t<-eps);}
double sq(double r){return r*r;}
/*
点的加减乘除赋值求叉积点积旋转
线对称得到线段，表达式
叉积
点在线段上
点p0到线段(p1-p2)距离
判断线段相交
极角排序
凸包模板
已知两点坐标，求国这两点的直线解析方程
如果两条直线l1(a1*x+b1*y+c1=0) ,l2(a2*x+b2*y+c2=0)相交,并且返回交点
判断点p是否在线段l上
如果线段seg1和seg2相交，返回true且交点由(inter)返回，否则返回false
线段与直线相交返回交点 
返回多边形面积(signed)
必须是逆时针的凸包方向输入顺序返回多边形顶点的凸凹性判断
判断的时候必须保证凸包是顺时针  
点q是凸多边形polygon内时，返回true
线段及直线的基本运算   
判断点与线段的关系
求点C到线段AB所在直线的垂足 P 
求点p到线段l的最短距离,并返回线段上距该点最近的点np 
计算点到折线集的最近距离,并返回最近点. 
判断圆是否在多边形内. //只能判断圆是否与多边形是否相交和圆心在多边形内部
对于已经排序（可以是顺序也可以是逆序）的多边形（可以是凸也可以是凹）求多边形的重心
向向量的左手方向推进
返回被切后多边形的点数(如果只剩一条线返回的点数也可能是正的)
半平面求交 输入的是直线
如果输入顶点按逆时针排列，返回true ，可以处理凸或者凹多边形，任意多边形
判断一个凸多边形（已经按照顺或者逆时针排序）是顺时针还是逆时针，并把顺时针改成逆时针
旋转卡壳的大概思路
圆模板
求包含now点以r为半径的圆最多可以覆盖多少其他点
*/
struct POINT
{
	double x,y;
	double angle;
	void rd(){scanf("%lf%lf", &x,&y);}
	POINT(){}
	POINT(double a,double b){x=a; y=b;}
	POINT operator-(const POINT a)const
	{	return POINT(x-a.x,y-a.y);}
	POINT operator+(const POINT &p)const
	{	return POINT(x+p.x,y+p.y);}
	POINT operator/(const double b)const
	{	return POINT(x/b,y/b);}
	POINT operator*(const double b)const
	{	return POINT(x*b,y*b);}
	bool operator>(const POINT a)const
	{ 	if(fabs(y-a.y)<eps)	return x>a.x;
		return y>a.y;}
	bool operator<(const POINT a)const
	{ 	if(fabs(y-a.y)<eps)	return x<a.x;
		return y<a.y;}
	bool operator==(POINT a)
	{ return dcmp(a.x-x)==0 && dcmp(a.y-y)==0;}

	
	POINT add(POINT p)
	{	return POINT(x+p.x,y+p.y);}
	POINT sub(POINT p)
	{	return POINT(x-p.x,y-p.y);}
	POINT mul(double b)
	{	return POINT(x*b,y*b);}
	POINT div(double b)
	{	return POINT(x/b,y/b);}
	double len()
	{	return sqrt(len2());}
	double len2()
	{	return x*x+y*y;}
	double dist(POINT p)
	{	return sqrt((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y));}
	double dot(POINT p)
	{	return x*p.x +y*p.y;}
	double det(POINT p)
	{	return x*p.y-y*p.x;}
	double rad(POINT a,POINT b)//求角apb的度数p为现在这一点
	{	POINT p =*this;
		return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));}
	
	POINT trunc(double r)
    {
        r/=len();
        return POINT(x*r,y*r);
    }//把向量截断成长度为a的向量
	POINT rotleft()
	{	return POINT(-y,x);}
	POINT rotright()
	{	return POINT(y,-x);}
	POINT rotate(POINT p,double angle)//绕点p逆时针旋转angle角度
	{
		POINT v=this->sub(p);
		double c=cos(angle),s=sin(angle);
		return POINT(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
	}
};
bool operator ==(const POINT &a,const POINT &b)
{
	if(a.x==b.x && b.y==a.y)	return true;
	else false;
}

struct SEG
{
	POINT p1,p2;
	POINT s,t;
	SEG(){}
	SEG(POINT a,POINT b){p1=a; p2=b;
	s=a; t=b;}
	void rd(){p1.rd();p2.rd();}
};
struct LINE
{
	double a,b,c;
	LINE(){}
	LINE(double aa,double bb,double cc)
	{
		a=aa;
		b=bb;
		c=cc;
	}
	POINT s,t;
	LINE(POINT ss,POINT tt)
	{s=ss; t=tt;}
	bool operator==(LINE v)
	{
		return (s==v.s)&&(t==v.t);
	}
	LINE(POINT p,double angle)
	{
		s=p;
		if(dcmp(angle-pi/2)==0)
			t=s.add(POINT(0,1));
		else
			t=s.add(POINT(1,tan(angle)));
	}
	void getpoint(double aa,double bb,double cc)
	{
		if(dcmp(aa)==0)
		{
			s=POINT(0,-cc/bb);
			t=POINT(1,-cc/bb);
		}
		else if(dcmp(bb)==0)
		{
			s=POINT(-cc/aa,0);
			t=POINT(-cc/aa,1);
		}
		else
		{
			s=POINT(0,-cc/bb);
			t=POINT(1,(-cc-aa)/bb);
		}
	}
	void rd()
	{	s.rd(); t.rd();}
	POINT lineprog(POINT p)//这个没太懂呢**********
    {
        return s.add(t.sub(s).trunc(t.sub(s).dot(p.sub(s))/t.dist(s)));
    }
    POINT symmetrypoint(POINT p)//点关于直线的对称点
    {
    	POINT q=lineprog(p);
    	return POINT(2*q.x-p.x,2*q.y-p.y);
    }	
};

double cross(POINT p2,POINT p3,POINT p1)//L12*L13
{   
 //大于0则向量p1p2（p2-p1)在向量p1p3(p3-p1)顺时针方向
 //小于0则向量p1p2（p2-p1） 在向量p1p3(p3-p1)逆时针方向
 //等于0则在同一直线上
  return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int add(int a,int b)
{
	return a=(a+1)%b;
}
int sub(int a,int b)
{
	return a=(a+b-1)%b;
}
int onseg1(POINT p1,POINT p2,POINT p3)//p3 在p1 和p2中间
{
	if(dcmp(min(p1.x,p2.x)-p3.x)<=0 && dcmp(p3.x-max(p1.x,p2.x))<=0 &&
	   dcmp(min(p1.y,p2.y)-p3.y)<=0 && dcmp(p3.y-max(p1.y,p2.y))<=0 
	)
		return 1;
	return 0;
}
//点积
/*点积 r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的点积，如果两个矢量都非零矢量 
r<0:两矢量夹角为钝角；r=0：两矢量夹角为直角；r>0:两矢量夹角为锐角 */
double dotmultiply(POINT p1,POINT p2,POINT p0)
{
	return ((p1.x-p0.x)*(p2.x-p0.x)+ (p1.y-p0.y)*(p2.y-p0.y));
}
//距离
double dist(POINT p1,POINT p2)//可以用hypot(p1.x-p2.x,p1.y-p2.y)代替
{
	double d1=p1.x-p2.x;
	double d2=p1.y-p2.y;
	return sqrt(d1*d1+d2*d2);
}
double dtwo(POINT p1,POINT p2)
{
	double d1=p1.x-p2.x;
	double d2=p1.y-p2.y;
	return (d1*d1+d2*d2);
}
//点p0到线段(p1-p2)距离
double disptoseg(POINT p0,POINT p1,POINT p2)
{
      if(dotmultiply(p0,p1,p2)<0||dotmultiply(p0,p2,p1)<0)
            return min(dist(p0,p1),dist(p0,p2));
      return fabs(cross(p1,p2,p0))/dist(p1,p2);
}


int onseg2(POINT p1,POINT p2,POINT p3)
{
	if(dcmp(p2.x- p1.x) ==0 )//在统一竖直线上
	{
		if(dcmp(min(p1.x,p2.x)-p3.x)==0 && 
		dcmp(min(p1.y,p2.y)-p3.y)<0 
		&&  dcmp(p3.y-max(p1.y,p2.y))<0  )	
			return 1;
		return 0;
	}
	if(dcmp(p1.y-p2.y)==0 )//统一水平线上
	{
		
		if(dcmp(min(p1.x,p2.x)-p3.x)<0 && dcmp(p3.x-max(p1.x,p2.x))<0 && dcmp(min(p1.y,p2.y)-p3.y)==0)
			return 1;
		return 0;
	}
	if(dcmp(min(p1.x,p2.x)- p3.x)<0 &&dcmp( p3.x-max(p1.x,p2.x))<0  &&
		 dcmp(min(p1.y,p2.y)-p3.y)<0 &&dcmp( p3.y-max(p1.y,p2.y))<0 )
		 	return 1;
	return 0;
}


//********判断线段相交****************/
int seginsec(SEG a ,SEG b)
{
//-1无交点
//0 平行无交点
//1 完全重合包括相等
//2 平行但是有无穷交点
//3 有端点交点
//4 有非端点交点
	double d1,d2,d3,d4;
	d1= cross(a.p2,b.p1,a.p1);
	d2= cross(a.p2,b.p2,a.p1);
	d3=	cross (b.p2,a.p1,b.p1);
	d4=	cross(b.p2,a.p2,b.p1);
	
	if(dcmp(d1*d2)<0 && dcmp(d3*d4)<0)
		return 4;
	
	if(dcmp(d1) ==0 && dcmp(d2)==0 && dcmp(d3)==0 && dcmp(d3) ==0 && dcmp(d4) ==0)
	{
		if(a.p1==b.p1 &&!onseg1(a.p1,a.p2,b.p2))	return 3;
		if(a.p1==b.p2 &&!onseg1(a.p1,a.p2,b.p1) )	return 3;
		if(a.p2==b.p1 &&!onseg1(a.p1,a.p2,b.p2))	return 3;
		if(a.p2==b.p2 &&!onseg1(a.p1,a.p2,b.p1) )	return 3;
		
		if(onseg2(a.p1,a.p2,b.p1) && onseg2(a.p1,a.p2,b.p2))	return 1;
		
		if(onseg1(a.p1,a.p2,b.p1) || onseg1(a.p1,a.p2,b.p2))	return 2;
	
		if(onseg2(b.p1,b.p2,a.p1) && onseg2(b.p1,b.p2,a.p2))	return 1;
	
		if(onseg1(b.p1,b.p2,a.p1) || onseg1(b.p1,b.p2,a.p2))	return 2;
		return 0;
	}
	if(dcmp(d1)==0 && onseg1(a.p1,a.p2,b.p1))	return 3;
	if(dcmp(d2)==0 && onseg1(a.p1,a.p2,b.p2))	return 3;
	if(dcmp(d3)==0 && onseg1(b.p1,b.p2,a.p1))	return 3;
	if(dcmp(d4)==0 && onseg1(b.p1,b.p2,a.p2))	return 3;
	return -1;
}

/*
POINT pangle;//极角排序 pangle是定位点
bool cmpangle(const POINT &a,const POINT &b)
{
	if(dcmp(a.angle-b.angle)==0)
		return dcmp(dist(a,pangle)-dist(b,pangle))<0;
	return a.angle<b.angle;
}
void anglesort(POINT po[],POINT now,int vn)
{
	int i;
	double the;
	POINT  tp;
	for(i=0; i<vn;i++)
	{
		tp=po[i]-now;
		the=atan2(tp.x,tp.y);
		if(dcmp(the)<0)
			the+=2*pi;
		po[i].angle=the;
	}	
	sort(po,po+vn,cmpangle);
}*/

/************凸包模板*************************/
//注意求凸包并不能保证求出的是凸多边形，有可能所有点都在一条直线上，这样可以用top指针《=2 来判断是否所有点在一条直线上
int top; //0到top-1是凸包点 ,第top个和第0个是相同的点
int cmp(POINT a,POINT b)
{
	if(dcmp(a.y-b.y)==0)	return dcmp(a.x-b.x)<0;
	 return  dcmp(a.y-b.y)<0;
}
//特别注意的是传进来的 点p经过了排序处理，顺序和以前不一样了
void graham(int n,POINT p[],POINT polygon[])//polygon是返回的凸包
{
    int i,j,temtop;
    if(n<=1)
    {
		top=1;
        polygon[0]=polygon[1]=p[0];return;
    }
    sort(p,p+n,cmp);
    top=-1;
    polygon[++top]=p[0];
    polygon[++top]=p[1];
    for(i=2; i<n; ++i)
    {
        while(top && 
        dcmp( cross(p[i],polygon[top],polygon[top-1] ))>=0)
            top--;
            polygon[++top]=p[i];
    }
    temtop=top;
     polygon[++top]=p[n-2];
    for(i=n-3;i>=0; i--)
    {
        while(top>=temtop+1 &&
         dcmp(cross(p[i],polygon[top], polygon[top-1]))>=0)
            top--;
        polygon[++top]=p[i];
    }
}
/************凸包模板*************************/



//已知两点坐标，求国这两点的直线解析方程  
 //a*x+b*y+c=0 (a>=0)
LINE makeline(POINT p1,POINT p2)
{
	LINE t;
	int sign=1;
	t.a=p2.y-p1.y;
	if(t.a<0)
	{
		sign=-1;
		t.a=sign*t.a;
	}
	t.b=sign*(p1.x-p2.x);
	t.c=sign*(p1.y*p2.x-p1.x*p2.y);
	return t;
}

//如果两条直线l1(a1*x+b1*y+c1=0) ,l2(a2*x+b2*y+c2=0)相交,并且返回交点
//-1 表示平行，0表示是重合的一条直线,1表示相交
int lineinsec(LINE l1,LINE l2,POINT &p)
{
	double d= l1.a*l2.b-l1.b*l2.a;
	double d1=l1.a*l2.c-l1.c*l2.a;
	double d2=l1.b*l2.c-l1.c*l2.b;
	if(dcmp(d)==0)
		if(dcmp(d1)==0 && dcmp(d2)==0)
			return 0;
		else return -1;
	p.x=d2/d;//p.x=(l2.c*l1.b-l1.c*l2.b)/d;
	p.y=-d1/d;//p.y=(l2.a*l1.c-l1.a*l2.c)/d;
	return 1;
}

// 判断点p是否在线段l上
//条件：(p在线段l所在的直线上)&& (点p在以线段l为对角线的矩形内) 
bool onseg(SEG l,POINT p)
{//如果不能在线段端点上，则要把<=改成<;
	return (dcmp(cross(p,l.p2,l.p1))==0 && (onseg1(l.p1,l.p2,p)));
}

//如果线段seg1和seg2相交，返回true且交点由(inter)返回，否则返回false 
bool seginsec(SEG seg1,SEG seg2,POINT &inter)
{
	LINE l1,l2;
	l1= makeline(seg1.p1,seg1.p2);
	l2= makeline(seg2.p1,seg2.p2);

	if(lineinsec(l1,l2,inter)==1)
	{
		return onseg(seg1,inter);
	}
	else return false;
}

//线段与直线相交返回交点
POINT segcrossline(SEG seg, LINE l) 
{
	 POINT g,s=seg.p1,t=seg.p2;
	 double a=l.a,b=l.b,c=l.c;
	 double u = fabs(a * s.x + b * s.y + c);   
	 double v = fabs(a * t.x + b * t.y + c);   
	 g.x=(s.x*v + t.x*u)/(u+v),g.y=(s.y*v+t.y*u)/(u+v);   
	 return g;
} 

//判断直线与线段是否相交， 线段V所在的直线与线段U相交时返回true,(线段u是否跨立线段v)
bool intersect(SEG u,SEG v)
{
    return  dcmp(cross(u.p1,v.p2,v.p1)*cross(v.p2,u.p2,v.p1))>=0;
}


//返回多边形面积(signed)
//输入顶点按逆时针排列时，返回正值；否则返回负值 
//返回浮点值==0.0时，说明不是多边形，没有面积。此函数同样适用于非凸多边形（wangkun的添加）
double area_polygon(int vcount ,POINT polygon[])
{
	if(vcount<3)	return 0;
	double s;
	s=polygon[0].y*(polygon[vcount-1].x-polygon[1].x);
	for(int i=1; i<vcount; i++)
		s+=polygon[i].y*(polygon[i-1].x-polygon[(i+1)%vcount].x);
	return s/2;
}

//必须是逆时针的凸包方向输入顺序返回多边形顶点的凸凹性判断
//返回值：，bc[i]=1,iff:第i个顶点是凸顶点 
void checkconvex(int vn ,POINT polygon[],bool bc[])
{
	int i,id=0;
	POINT tp=polygon[0];
	for(i=1; i<vn ; i++)//寻找第一个凸点
	{
		if(polygon[i].y< tp.y || (polygon[i].y == tp.y && polygon[i].x< tp.x))
		{
			tp=polygon[i];
			id=i;
		}
	}
	double s;
	int count =vn -1;
	bc[id]=true;
	while(count )
	{
		 if (dcmp( 
	cross(polygon[(id+1)%vn], polygon[(id+2)%vn] ,polygon[id]) 
	         )>=0)
			 bc[(id+1)%vn]=true;
		 else
		 {
		 	 bc[(id+1)%vn]=false;
		 }
		 id=add(id,vn);
		 count--;
		 
	}
}
//判断的时候必须保证凸包是逆时针
//返回值：多边形polygon是凸多边形时，返回true  
bool isconvex(int vn ,POINT polygon[])
{
	bool bc[maxn];
	checkconvex(vn ,polygon,bc);
	for(int i=0; i<vn ;i++)// 逐一检查顶点，是否全部是凸顶点 
		if(!bc[i])
			return false;
	return true;
	
}
//点q是凸多边形polygon内时，返回true；
//注意：多边形polygon一定要是凸多边形 （因为要求多边形内部一点）
bool InsideConvexPolygon(int vcount ,POINT polygon[],POINT q)
{
	POINT p;
	SEG l;
	int i;
	p.x=0;p.y=0;
	for(i=0; i<vcount ;i++)// 寻找一个肯定在多边形polygon内的点p：多边形顶点平均值 
	{
		p.x+=polygon[i].x;
		p.y+=polygon[i].y;
	}
	p.x/=vcount;
	p.y/=vcount;
	for(i=0; i<vcount ; i++)
	{
		l.p1= polygon[i]; l.p2=polygon[(i+1)%vcount];
		if(dcmp(cross(p,l.p2,l.p1)* cross(q,l.p2,l.p1)) <0)
			break;
	}
	return (i==vcount);
}

/*
线段及直线的基本运算   
判断点与线段的关系,
用途很广泛 
本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足 

                AC dot AB 
        r =     --------- 
                 ||AB||^2 
             (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay) 
          = ------------------------------- 
                          L^2 

    r has the following meaning: 

        r=0      P = A 
        r=1      P = B 
        r<0 P is on the backward extension of AB 
r>1      P is on the forward extension of AB 
        0<r<1 P is interior to AB 
*/ 
double relation(POINT p,SEG l)
{
	SEG tl;
	tl.p1=l.p1;
	tl.p2=p;
	return dotmultiply(tl.p2,l.p2,l.p1)/(dist(l.p1,l.p2)*dist(l.p1,l.p2));
}
//求点C到线段AB所在直线的垂足 P 
POINT perpendicular(POINT p,SEG l,double r)
{
	//double r = relation(p,l);
	POINT tp;
	tp.x= l.p1.x+r*(l.p2.x-l.p1.x);
	tp.y= l.p1.y +r*(l.p2.y-l.p1.y);
	return tp;
}

//求点p到线段l的最短距离,并返回线段上距该点最近的点np 
//注意：np是线段l上到点p最近的点，不一定是垂足 
double ptolinesegdist(POINT p,SEG l,POINT &np)
{
	double r=relation(p,l);
	if(r<0)
	{
		np= l.p1;
		return dist(p,l.p1);
	}
	if(r>1)
	{
		np = l.p2;
		return dist(p,l.p2);
	}
	np = perpendicular(p,l,r);
	return dist(p,np);
}
//计算点到折线集的最近距离,并返回最近点. 
//注意：调用的是 ptolinesegdist()函数 
double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q)
{
	int i;
	double cd=double(inf),td;
	SEG l;
	POINT tq,cq;
	for(i=0; i<vcount-1; i++)
	{
		l.p1=pointset[i];
		l.p2=pointset[i+1];
		td=ptolinesegdist(p,l,tq);
		if(td<cd)
		{
			cd=td;
			cq=tq;
		}
	}
	q=cq;
	return cd;
}
// 判断圆是否在多边形内. //只能判断圆是否与多边形是否相交和圆心在多边形内部
bool CircleInsidePolygon(int vcount ,POINT center,double radius,POINT polygon[])
{
	if(!InsideConvexPolygon(vcount ,polygon,center))
		return false;
	POINT q;
	double d;
	q.x=0;q.y=0;
	d=ptopointset(vcount,polygon,center,q);	
	 
	if( dcmp(d-radius)>=0 )//注意相切的情况
		return true;
	else 
		return false;
}         

/*对于已经排序（可以是顺序也可以是逆序）的多边形（可以是凸也可以是凹）求多边形的重心*/
POINT gravitycenter(int vcount ,POINT polygon[])
{
    POINT tp;int i;
    double x,y,s,x0,y0,cs,k;
    x=0; y=0; s=0;
    for(i=1; i<vcount-1; i++)
    {
        x0=(polygon[0].x+polygon[i].x+polygon[i+1].x)/3;
        y0=(polygon[0].y+polygon[i].y+polygon[i+1].y)/3;
        cs=cross(polygon[i],polygon[i+1],polygon[0])/2;
        s+=cs;
        x+=cs*x0;
        y+=cs*y0;
    }
    tp.x=x/s;
    tp.y=y/s;
    return tp;
}
inline void tuijin(POINT &p1,POINT &p2,double d)//逆时针的两个点想凸包内推进，顺时针向外
//向向量的左手方向推进
{
	// printf("d=%lf %lf %lf %lf %lf\n",d,p1.x,p1.y,p2.x,p2.y);
	 double px,py,l;
	 px=-p2.y+p1.y; py=p2.x-p1.x;
	 l=sqrt(px*px+py*py);
	 px=d*px/l; py=d*py/l;
	 p1.x+=px;
	 p2.x+=px;
	 p1.y+=py;
	 p2.y+=py;
	 // printf("d=%lf %lf %lf %lf %lf\n",d,p1.x,p1.y,p2.x,p2.y);
}


//半平面求交 输入的是直线
//点数为2则必然不能构成凸包是直线,大于等于3必然构成凸包不能都是一个直线上的点
int cutpolygon2(POINT poly[],int vn,LINE l)
{// 直线切割方向是ax+by+c<=0方向的
	double a=l.a,b=l.b,c=l.c;
	int nn=0,j;
	POINT pp[maxn];
	poly[vn]=poly[0];//这句一定要
	for(int i=0;i<=vn; i++)//注意第一个和最后一个之间的检查
	{
		if(dcmp(a*poly[i].x + b*poly[i].y +c)<=0)//如果在边界上也加入新凸包
			pp[nn++]=poly[i];
		else
		{//注意边界情况不要多算了,边界情况加在上面
		if(i>0 && dcmp(a*poly[i-1].x + b*poly[i-1].y +c)<0)//入界情况
			pp[nn++]=segcrossline(SEG(poly[i-1],poly[i]),l);
		if(i<vn && dcmp(a*poly[i+1].x+b*poly[i+1].y +c)<0)//出界情况
			pp[nn++]=segcrossline(SEG(poly[i],poly[i+1]),l);
		}
	}
	for(int i=0; i<=nn; i++) poly[i]=pp[i];//这里赋值了 nn点
	return nn;
}

//半平面交模板，多边形要是逆时针方向，可以处理凹多边形，s-t的切割方向为从s到t的左手系方向掌心朝上，大拇指的方向
//o是半平面交的顶点,st是有向线段,他们满足dcmp(cross(t,o,s))>=0
int cutpolygon3(POINT poly[],int vn,POINT s,POINT t)//返回新的多边形的点数
{
	LINE l=makeline(s,t);
	int nn=0,j;
	POINT pp[maxn];
	poly[vn]=poly[0];
	for(int i=0; i<vn; i++)
	{
		if(dcmp(cross(t,poly[i],s))>=0)
		{
			pp[nn++]=poly[i];
			if(dcmp(cross(t,poly[add(i,vn)],s))<0)
			{
				pp[nn++]=segcrossline(SEG(poly[i],poly[add(i,vn)]),l);
			}
		}
		else if(dcmp(cross(t,poly[add(i,vn)],s))>0)
		{
			pp[nn++]=segcrossline(SEG(poly[i],poly[add(i,vn)]),l);
		}
	}
	for(int i=0; i<=nn; i++)	poly[i]=pp[i];
	return nn;
}
// 如果输入顶点按逆时针排列，返回true ，可以处理凸或者凹多边形，任意多边形
void isconterclock(int vn,POINT polygon[]) 
{ 
	if(area_polygon(vn,polygon)<=0)
		 reverse(polygon,polygon+vn); 
} 

//判断一个凸多边形（已经按照顺或者逆时针排序）是顺时针还是逆时针，并把顺时针改成逆时针
void anticlockwise(POINT *polygon,int len)//传入凸包和点数
{
    for(int i=0;i<len-2;i++)
    {
        double tmp=cross(polygon[i+1],polygon[i+2],polygon[i]);
        if(dcmp(tmp)>0)
            return;
        else if(dcmp(tmp)<0)
        {
            reverse(polygon,polygon+len);
            return;
        }
    }
}
//旋转卡壳的大概思路
double rotatecaliper(POINT *s,POINT *t,int lenn,int lenm)//旋转卡壳求两个点的最近距离
{
	double ans,del;
	int i1,i2,i,j,ni,nj,j1,j2;
	POINT tp=s[0];
	i1=0;
	for(i=0; i<lenn; i++)
	if(tp>s[i])
	{
		tp=s[i];
		i1=i;
	}
	tp=t[0];
	i2=0;
	for(i=0; i<lenm; i++)
	if(tp<t[i])
	{
		tp=t[i];
		i2=i;
	}
	ans=inf;
	int s1=i1,s2=i2;//取最极端两边的两个平行点
	while(1)
	{
		j1=i1;j2=i2;
		add(j1,lenn);add(j2,lenm);
		ans=min(ans,disptoseg(s[i1],t[i2],t[j2]));
		ans=min(ans,disptoseg(s[j1],t[i2],t[j2]));
		ans=min(ans,disptoseg(t[i2],s[i1],s[j1]));
		ans=min(ans,disptoseg(t[j2],s[i1],s[j1]));
		del=cross(s[j1]-s[i1],t[j2]-t[i2],POINT(0,0));
		if(dcmp(del)==0)	add(i1,lenn),add(i2,lenm);
		else if(dcmp(del)<0)	add(i1,lenn);
		else add(i2,lenm);
		if(i1==s1 && i2==s2)	break;
	}
	return ans;
}
struct circle
{
	POINT p;
	double r;
	circle(){}
	circle(POINT pp,double rr){p=pp; r=rr;}
	circle(double x,double y,double rr)
	{ p=POINT(x,y); r=rr;}//三点确定园要写一下
	//得到圆中以a为角度的弓形（就是扇形减去三角形）
	double areagongxing(double a){return sq(r)*(a-sin(a))/2;}
	void rd()
	{
		p.rd();scanf("%lf",&r);
	}
	bool operator==(circle v)
	{
		return ((p==v.p) && dcmp(r-v.r)==0);
	}
	double area()
	{
		return pi*sq(r);
	}
	double cirlen()//周长
    {
    	return 2*pi*r;
    }
    int relation(POINT b)//0圆外，1圆上,2圆内
    {
    	double d=b.dist(p);
    	if(dcmp(d-r)==-1)	return 2;
    	else if(dcmp(d-r)==0)	return 1;
    	return 0;
    }
     //5 相离
	//4 外切
	//3 相交
	//2 内切
	//1 内含 
    int relationcircle(circle v)//圆的关系 
    {
    	double d=dist(p,v.p);
    	if (dcmp(d-r-v.r)>0)return 5; //5 相离
    	if (dcmp(d-r-v.r)==0)return 4;//4 外切
    	double l=fabs(r-v.r);
    	if (dcmp(d-r-v.r)<0&&dcmp(d-l)>0)return 3;//3 相交
    	if (dcmp(d-l)==0)return 2;//2 内切(包括两圆相等)
    	if (dcmp(d-l)<0)return 1;//1 内含 

    }
    double areacircle(circle v)//圆相交
    {
    	int rel=relationcircle(v); 
    	if (rel>=4)return 0.0;
  	  	if (rel<=2)return min(area(),v.area());
  	  	double l = p.dist(v.p);
  	  	double h1=(sq(r)-sq(v.r)+sq(l))/(2*l);
    	double len= sqrt(sq(r)-sq(h1));
    	double h2=l-h1;
    	double the1=acos(h1/r);
    	double the2=acos(h2/v.r);
    	return the1*sq(r)+the2*sq(v.r)-len*l;
    }
};    

/********************///求包含now点以r为半径的圆最多可以覆盖多少其他点poj1981
struct nod
{	double theta;int a,flag;
    nod(){}
    nod(double aa,int  cc)
    {theta=aa;  flag=cc;}
    bool operator<(const nod &b)const 
	{
        return dcmp(theta-b.theta)<0;
	}
}f[702100];
int fcnt;
//求包含now点以r为半径的圆最多可以覆盖多少其他点
int circlegetdot(int now,POINT poly[],double r,int vn)
{
	 fcnt=0;
	int i,j;
	for(j=0; j<vn; j++)
	if(now!=j)
	{
		    double theta,phi,d;
		    d=poly[now].dist(poly[j]);//j到now点的距离
		    if(dcmp(d-2*r)>0)//两点距离大于直径不考虑
		        continue;
		   //关键部分
		    POINT tp=poly[j].sub(poly[now]);
		    theta=atan2(tp.y,tp.x);//求直线now-j的倾角
		    if(dcmp(theta)<0)
		        theta+=2*pi;//为方便极角排序,对于负角要+2pi。
		    phi=acos(d/(2*r));
		    //为方便极角排序,每个极角均加 2pi,使域扩张到[0,4pi],从而防止了跨 0 角的出
		    f[fcnt++]=nod(theta-phi+2*pi,1);//逆时针前面的点
		    f[fcnt++]=nod(theta+phi+2*pi,-1);
		   // 接下来,对于每个圆上的 t(偶数)个极角进行排序,再顺序扫描,动态更新最大值。
	}
	sort(f,f+fcnt);//犄角排序
	int ans=1;//包含now点不能为0要注意
	int sum=1;//包含now点
	for(j=0; j<fcnt; j++)//这道题是要求最多可以有多少个点在以r半径的圆内
    {
            sum+=f[j].flag;
        ans=max(ans,sum);
    }
    return ans;
}
/********************///求包含now点以r为半径的圆最多可以覆盖多少其他点
/**********最近点对模板***************/
bool cmpx(POINT a,POINT b)
{
    return a.x<b.x;
}
bool cmpy(POINT a,POINT b)
{
    return a.y<b.y;
}
POINT num[10];
POINT ano[30];//最近点对里面需要的数组用来对y排序
double pointmindist(int l,int r)
{
    if(r-l==1) return dist(num[l],num[r]);
    if(r-l==2) 
    return min(min(dist(num[l],num[l+1]),dist(num[l],num[r])),dist(num[l+1],num[r]));
    int mid=(l+r)/2;
    
    double now=min(pointmindist(l,mid),pointmindist(mid+1,r));
    int k=0;
    
    for(int i=mid;i>=l&& dcmp(num[mid+1].x-num[i].x-now)<0;i--)
    {
        ano[k++]=num[i];
    }
    for(int i=mid+1;i<=r&& dcmp(num[i].x-num[mid].x-now)<0;i++)
    {
        ano[k++]=num[i];
    }
    
    sort(ano,ano+k,cmpy);
    for(int i=0;i<k;i++)
    {
        for(int j=i+1;j<k&& dcmp(ano[j].y-ano[i].y-now)<0;j++)
        {
            now=min(now,dist(ano[j],ano[i]));
        }
    }
    return now;
}
/**********最近点对模板***************/
/***********三点的外接圆****三角形的外接圆***********************/
int iscircle(POINT p1,POINT p2,POINT p3,POINT &q,double &r)
{
	double x12,y12,x13,y13,z2,z3,d;
	x12=p2.x-p1.x;
	y12=p2.y-p1.y;
	x13=p3.x-p1.x;
	y13=p3.y-p1.y;
	z2=x12*(p1.x+p2.x)+y12*(p1.y+p2.y);
	z3=x13*(p1.x+p3.x)+y13*(p1.y+p3.y);
	d=(x12*(p3.y-p2.y)-y12*(p3.x-p2.x))*2;
	if(dcmp(d)==0)
		return 0;
	q.x=(y13*z2-y12*z3)/d;
	q.y=(x12*z3-x13*z2)/d;
	r=dist(p1,q);
	return 1;
}
/***********三点的外接圆****三角形的外接圆***********************/
/************最小圆覆盖模板*******************************/
void mincircle(POINT p[],int vn,POINT &c,double &r)
{
	random_shuffle(p,p+vn); // 重点 只是为了省时间的随机
	int i,j,k,q;
	c=p[0]; r=0;

	for(i=1; i<vn; i++)
	if(dcmp(dist(p[i],c)-r)>0)
	{
		c=p[i]; r=0;
		for(k=0; k<i; k++)
		if(dcmp(dist(p[k],c)-r)>0)
		{
			c=p[i].add(p[k]);
			c=c.div(2);
			r=dist(p[k],c);
			for(j=0; j<k; j++)
			if(dcmp(dist(p[j],c)-r)>0)
			{
				q=iscircle(p[i],p[k],p[j],c,r);
			}
		}		
	}
}
/************最小圆覆盖模板*******************************/

/******点到直线的距离***********/
double disptoline(POINT p,POINT l1,POINT l2)//点到直线的距离
{//a*b = |a||b|sin<a,b>  => 所有为|b|sin<a,b>
	return fabs(cross(l1,l2,p))/dist(l1,l2);
}
//返回l1和l2所在的直线和圆是否相交，返回两个交点(两个交点可能相等)
//0表示不相交 ,1表示两个交点相同，2表示两个不同的交点
int intersectionlinecircle(POINT l1,POINT l2,POINT &p1,POINT &p2,POINT o,double r)
{
	double d=disptoline(o,l1,l2),t;
	if(dcmp(d-r)>0)	return 0;
	
	POINT p=o.add(POINT(l1.y-l2.y,l2.x-l1.x));
	lineinsec(makeline(l1,l2),makeline(p,o),p);
	t=sqrt(r*r-dist(p,o)*dist(p,o))/dist(l1,l2);
	p1=POINT(p.x+(l2.x-l1.x)*t,p.y + (l2.y - l1.y) * t);
	p2=POINT(p.x - (l2.x - l1.x) * t,p.y - (l2.y - l1.y) * t);
	if(dcmp(d-r)==0)	return 1;
	return 2;
}

/**判断三角形剖分(两点是a,b 是多边形的点，另外一点在圆上)和圆相交的有向面积***/
double tricirclecross(POINT a,POINT b,POINT o,double r)
{//传入有向线段a b,圆心坐标o ,圆半径r //POJ    3675
	double is=cross(a,b,o);
	if(dcmp(is)==0)	return 0;
	double ans=0;
	double d=disptoline(o,a,b);
	double da=dist(a,o);
	double db=dist(b,o);
	if(dcmp(d-r)<0)
	{
		if(dcmp(da-r)<=0 && dcmp(db-r)<=0)//线段都在圆内
			ans=cross(a,b,o)/2;
		else
		{
			double ta=0,A;//A是角度
			POINT p1,p2;//交点
			intersectionlinecircle(a,b,p1,p2,o,r);
			bool onp1=onseg(SEG(a,b),p1);//判断p1是否在线段a,b上
			bool onp2=onseg(SEG(a,b),p2);//判断p2是否在线段a,b上
			if(onp1 && !onp2)//p1在ab上
			{
				if(dcmp(db-r)>0 && dcmp(da-r)<=0)//点b在圆外,a在圆内
				{
					A = acos(dotmultiply(p1,b,o)/(r*db));
                    ta = A*r*r/2;
                    ta += fabs(cross(o,a,p1)/2);
				}
				else
				{
					A = acos(dotmultiply(p1,a,o)/(r*da));
                    ta = A*r*r/2;
                    ta += fabs(cross(o,b,p1)/2);
				}
			}
			else if(onp2 && !onp1)//p2在a,b 上
			{
				if(dcmp(db-r)>0 && dcmp(da-r)<=0)//点b在圆外,a在圆内
				{
				    A = acos(dotmultiply(p2,b,o)/(r*db));
                    ta = A*r*r/2;
                    ta += fabs(cross(o,a,p2)/2);
				}
				else
				{
					A = acos(dotmultiply(p2,a,o)/(r*da));
                    ta = A*r*r/2;
                    ta += fabs(cross(o,b,p2)/2);
				}
			}
			else if(onp1 && onp2)
			{
				A = acos(dotmultiply(p1,a,o)/(r*da));
                ta = A*r*r/2;
                A = acos(dotmultiply(p1,p2,o)/(r*r));
                double tmp = A*r*r/2;
                if (dcmp(ta - tmp) >= 0)
                {
                    A = acos(dotmultiply(p2,a,o)/(r*da));
                    ta = A*r*r/2;
                    A = acos(dotmultiply(p1,b,o)/(r*db));
                    ta += A*r*r/2;
                }else
                {
                    A = acos(dotmultiply(p2,b,o)/(r*db));
                    ta += A*r*r/2;
                }
                ta += fabs(cross(o,p1,p2)/2);
			}
			else if(!onp1 && !onp2)
			{
				A = acos(dotmultiply(a,b,o)/(db*da));
                ta = A*r*r/2;
			}
			if(dcmp(cross(a,b,o))>0)
				ans+=ta;
			else ans-=ta;
		}
	}
	else //线段在圆外
	{
		double A = acos(dotmultiply(a,b,o)/(da*db));
        if (dcmp(cross(o,a,b)) > 0)
            ans += A*r*r/2;
        else ans -= A*r*r/2;
	}
	return ans;
}

//标号从0到vn-1,的一个可凹可凸多边形和以o为圆形，r为半径的圆的相交面积
double polycrosscircle(POINT p[],int vn,POINT o,double r)
{
	p[vn]=p[0];
	double ans=0;
	for(int i=0; i<vn; i++)	
    		ans+=tricirclecross(p[i],p[i+1],o,r);
	return ans;
}


/**************扫描线扫半个圆的方法*******************
int solve(int vn)
{//扫描线扫半个圆的方法，可以把点先极角排序后，然后把点数扩大两倍，这样就可以扫2*n次，不用判重就可以
	if(vn==2)	return 2;
	POINT now=c.p;
	int ans=0;
	int i,j;
	for(i=0; i<vn; i++)
		po[i]=p[i];
	
	anglesort(po,now,vn);
	for(i=vn; i<vn*2; i++)
		po[i]=po[i-vn];//把点扩大两倍
	j=0;
	int tp=0;
	for(i=0; i<2*vn; i++)
	{
		while(j<2*vn)//防止扫出现在的起点的判断
		{
			if(dcmp(cross(po[j],po[i],now))<0)	break;
			tp++;
			j++;
			if(j-vn==i) break;
		}
		ans=max(ans,tp);
		tp--;
	}
	return ans;
}
/***********扫描线扫半个圆的方法**********************/
POINT po[1],pangle;//极角排序 pangle是定位点
bool cmpangle(const POINT &a,const POINT &b)
{
	if(dcmp(a.angle-b.angle)==0)
		return dcmp(dist(a,pangle)-dist(b,pangle))<0;
	return a.angle<b.angle;
}
void anglesort(POINT po[],POINT now,int vn)
{
	int i;
	double the;
	POINT  tp;
	for(i=0; i<vn;i++)
	{
		tp=po[i]-now;
		the=atan2(tp.x,tp.y);
		if(dcmp(the)<0)
			the+=2*pi;
		po[i].angle=the;
	}	
	sort(po,po+vn,cmpangle);
}

/**************扫描线扫半个圆的方法*******************
circle c;
int solve(int vn)
{//扫描线扫半个圆的方法，可以把点先极角排序后，然后把点数扩大两倍，这样就可以扫2*n次，不用判重就可以
	if(vn==2)	return 2;
	POINT now=c.p;
	int ans=0;
	int i,j;
	for(i=0; i<vn; i++)
		po[i]=p[i];
	
	anglesort(po,now,vn);
	for(i=vn; i<vn*2; i++)
		po[i]=po[i-vn];//把点扩大两倍
	j=0;
	int tp=0;
	for(i=0; i<2*vn; i++)
	{
		while(j<2*vn)//防止扫出现在的起点的判断
		{
			if(dcmp(cross(po[j],po[i],now))<0)	break;
			tp++;
			j++;
			if(j-vn==i) break;
		}
		ans=max(ans,tp);
		tp--;
	}
	return ans;
}
/***********扫描线扫半个圆的方法**********************/

double angle(POINT o,POINT a,POINT b)//求角aob
{
	double d1=dist(a,o);
	double d2=dist(b,o);
	double ang=acos(dotmultiply(a,b,o)/d1/d2);
	//printf("%lf\n",ang);
	return ang;
}
double dirangle(POINT o,POINT a,POINT b)//ob顺时针旋转到oa的角度,逆时针的多边形角
{
	double d=cross(a,b,o);
	double ang=angle(o,a,b);
	if(dcmp(d)>=0)
		return ang;
	return 2*pi-ang;
}

POINT bianhuan(double the,POINT o,POINT t,POINT s,POINT now)//仿射变换
{//传入角度，绕o点旋转，t为平移向量，s为缩放向量,now 是现在的点
	POINT tp;
	tp.x=s.x*now.x+t.x;
	tp.y=s.y*now.y+t.y;
	tp=tp.rotate(o,the);
	return tp;
}
bool insidepolygon(POINT q,int vn,POINT p[],bool onedge=true)
{//判断点是否在任意多边形内，传入onedge=false 那么就不统计边界上的点
	POINT tp;
	int i=0,count=0;
	p[vn]=p[0];
	while(i<vn)
	{
		tp.x=rand()+inf;
		tp.y=rand()+inf;
		
		for(count=i=0; i<n; i++)
		{
			if(dcmp(cross(q,p[i],p[i+1]))==0 && 
			dcmp((p[i].x-q.x)*(p[i+1].x-q.x))<=0 &&
			dcmp((p[i].y-q.y)*(p[i+1].y-q.y))<=0 )
				return onedge;
		
			else if(0==dcmp(cross(q,tp,p[i])))	break;
			else if(dcmp(cross(q,p[i],tp)*cross(q,p[i+1],tp))<0 && 
				dcmp(cross(p[i],q,p[i+1])*cross(p[i],tp,p[i+1]))<0)
					count++;
		}
	}
	return count&1;
}

//判断两圆相交并返回交点，要先判交不交,如果是相交并且有一个以上交点才能用此函数
void circlejiao(circle c,circle d,POINT &s,POINT &t)
{//求出两点沿着圆C 逆时针排列的
	POINT a=c.p,b=d.p;
	double r1=c.r,r2=d.r,now,tp,tn;
	now=dtwo(a,b),tn=dist(a,b);
	tp=(sq(r1)-sq(r2)+now)/(2*r1*tn);
	POINT u=(b-a)/tn,v=POINT(-u.y,u.x)*(r1*sqrt(1-sq(tp)));
	POINT x=a+u*(r1*tp);
	s=x+v;t=x-v;
}
/************求多圆面积并***************************
struct event{
	double ang;
	int is;
	POINT p;
	event(){}
	event(double aa,int bb,POINT cc)
	{		ang=aa; is=bb;p=cc;			}
	bool operator<(const event a)const{
		if(dcmp(ang-a.ang)==0)	
			return is>a.is;
		return dcmp(ang-a.ang)<0;
	}
}eve[10000];
bool cmpp(circle a,circle b)
{
	return dcmp(a.r-b.r)>0;
}
circle tc[10000];
double circlrunion(circle cir[],int nn)//n^2*log(n)cir会被排序
{
//(1) 去掉包含(内含 or 内切)了某些圆的大圆
//(2) 去掉相同的圆
//(3) 如果存在2个圆不交，则直接返回 0 (交集必然为空)
	int i,j,k=0,flag,l,nc;
	double ans=0;
	int vn=0;
	sort(cir,cir+n,cmpp);//按照半径大小排序 
	for(i=0; i<nn; i++)
	{
		for(flag=0,j=0; j<vn; j++)
		if(i!=j&& cir[i].relationcircle(tc[j])<=2)//去掉包含的情况
		{
			flag=1;
			break;
		}
		if(!flag)
			tc[vn++]=cir[i];
	}
	for(i=0; i<vn;i++)
	{
		l=0,nc=0;
		POINT a,b,s,t,d =POINT(- tc[i].r, 0) + tc[i].p;
		//加两个边界 
		eve[l++]=event(-pi,1, d);eve[l++]=event( pi, -1, d);
		for(j = 0; j < vn; ++ j) 
		if(i!=j)
		{
			if(tc[i].relationcircle(tc[j])>=4)//没有两个的交点
				continue;
			circlejiao(tc[i],tc[j],a,b);//求交点
			s=a-tc[i].p;t=b-tc[i].p;
			double ang1=atan2(s.y,s.x),ang2=atan2(t.y,t.x);
			if(dcmp(ang2-ang1)>0)//记录有多少区间是正常的，其他跨了-pi
				++nc;//记录有多少个区间跨了-pi到pi这个地方
			eve[l++]=event(ang1,-1,a);//求角度
			eve[l++]=event(ang2,1,b);//假设ang2应该小于ang1
		}
		sort(eve,eve+l);
		double now=-pi;
		POINT tp=d;
		for(j=0; j<l; j++)
		{
		  nc+=eve[j].is;
		  if((nc==2 && eve[j].is>0 ) || nc==0)//只被覆盖一次的弧
		  {//这步求面积因为都要除以2，（如果精度不够）可以先加和，最后除以2
		  	ans+=tc[i].areagongxing(eve[j].ang-now);//算弓形面积 1
			ans+=cross(tp,eve[j].p,POINT(0,0))/2;//算多边形有向面积
		  }//tp,eve[j].p就是相交的多边形的边
		  now=eve[j].ang; tp=eve[j].p;
		}
	}
	return ans;
}
***************求多圆面积并*************************/
POINT p[2000],a,b;
SEG seg[100000];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	//freopen("out","w",stdout);
#endif
	int i,j,k,t,cas=0,cnt;
	while(n=rd(),n)
	{
		cnt=0;
		p[0]=POINT(0,0);
		p[1]=POINT(0,1000);
		p[2]=POINT(1000,1000);
		p[3]=POINT(1000,0);
		seg[cnt++]=SEG(p[0],p[1]);
		seg[cnt++]=SEG(p[1],p[2]);
		seg[cnt++]=SEG(p[2],p[3]);
		seg[cnt++]=SEG(p[3],p[0]);
		int ans=1;
		for(i=0; i<n ;i++)
		{
			k=0;
			a.rd(); 
			b.rd();
			SEG tp=SEG(a,b);
			for(j=0; j<cnt; j++)
			{
				if(seginsec(tp,seg[j],a))
				{
					p[k++]=a;	
				}
			}
			sort(p,p+k);
			k=unique(p,p+k)-p;
			ans+=k;
		}
		printf("%d\n",ans);
	}
}
